package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-05-04 15:09
 */
public class BuyAndSellSocketWithFee {
    /**
     * 五部曲：1.dp[i][0]:持有股票的最大利润 dp[i][1] 不持有股票的最大利润2.递推公式dp[i][0]=Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
     *             dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee); 遍历顺序：从前往后遍历 初始化 dp[0][0]=-prices[i] dp[1][0]=0
     * @param prices
     * @param fee
     * @return
     */
    public int maxProfit(int[] prices, int fee) {
        //定义dp数组
        int[][]dp=new int[prices.length][2];
        //初始化
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        //进行遍历
        for(int i=1;i<prices.length;++i){
            dp[i][0]=Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i]-fee);
        }
        return dp[prices.length-1][1];
    }
}
